NP (klasa kompleksnosti)
![](http://upload.wikimedia.org/wikipedia/bs/thumb/f/f7/P_np_np-kompletno_np-te%C5%A1ko.svg/300px-P_np_np-kompletno_np-te%C5%A1ko.svg.png)
U teoriji kompleksnosti, NP (nedeterminističko polinomijalno) je skup problema odluke, rješivih u polinomijalnom vremenu na nedeterminističkoj Turingovoj mašini. Ekvivalentno, to je skup problema čija rješenja mogu da se provjere na determinističkoj Turingovoj mašini u polinomijalnom vremenu.
NP se može smatrati kao skup problema odluke (odgovor 'da' ili 'ne') za koji se 'da'-rješenje u polinomijalnom vremenu može provjeriti sa determinističkom Turingovom mašinom. Problemi odluka za koje se 'ne'-rješenje jednostavno može kontrolisati, pripada Co-NP-u (komplement NP-a).
Formalna definicija
[uredi | uredi izvor]NP se može definisati sa pojmom NTIME[2][3]:
Alternativna definicija se može stvoriti koristeći determinističke Turing mašine kao verifikatore. Nadalje, jezik L je u NP-u ako i samo ako postoje polinomi p i q, i deterministička Turing mašina M, tako da
- za sve x i y, mašina M ima algoritamsko trajanje procesa p(|x|) sa ulaznim podacima (x,y).
- za svaki x koji je u L-u, postoji niz y dužine q(|x|) tako da je M(x,y) = 1.
- za svaki x koji nije u L-u i za sve nizove y dužine q(|x|), M(x,y) = 0.
Uvod
[uredi | uredi izvor]Klasa NP obuhvata mnoge prirodne probleme koji se formalno mogu definisati u računarstvu, kao na primjer što su odlučne verzije problema pretrage i optimizacije.
![]() | Ovaj odlomak potrebno je proširiti. |
Primjeri
[uredi | uredi izvor]Primjeri NP problema su:
- Problem izomorfizma grafova: odrediti da li su dva grafikona izomorfno identična.
- Problem faktorizacije cijelih brojeva: sa datim cijelim brojevima n i k, da li postoji faktor f tako da 1 < f < k i da je f djelioc broja n.
- Svi problemi u klasi P.
- Svi NP-kompletni problemi kao:
- Problem trgovačkog putnika: gdje pokušavamo da utvrdimo da li postoji put određene dužine koji obilazi sve čvorove.
- Problem zadovoljivosti: gdje želimo da utvrdimo da li je neka formula, iskazana u bulovskim promjenljivama, zadovoljiva ili ne.
Zašto je teško određene NP probleme riješiti
[uredi | uredi izvor]Pošto su mnogi važni problemi u ovoj klasi, ulagani su intenzivni napori da se nađu algoritmi u polinomijalnom vremenu za probleme u NP klasi. Međutim, veliki broj NP problema ostaje izazivajući ove pokušaje, koji dalje izgleda da zahtjevaju super-polinomijalno vrijeme. Da li ovi problemi stvarno nisu riješivi u polinomijalnom vremenu je jedno od najvećih otvorenih pitanja u računarstvu (P=NP problem).
Važan pojam u ovom kontekstu predstavlja skup NP-kompletnih problema odluke, koji su podskup klase NP, i neformalno se mogu opisati kao najteži NP problemi. Ako bi postojao algoritam u polinomijalnom vremenu za makar jedan od njih, onda bi postojao polinomijalni algoritam za sve probleme iz klase NP. Zbog ovoga, i zato što do sada (uprkos svim naporima) nije pronađen polinomijalni algoritam ni za jedan NP-kompletan problem, kada se za neki problem pokaže da je NP-kompletan, obično se smatra da nije vjerovatno da postoji polinomijalni algoritam za taj problem.
Vanjski linkovi
[uredi | uredi izvor]Literatura
[uredi | uredi izvor]- (en) R. E. Ladner, On the structure of polynomial time reducibility, J.ACM, 22, 1975. doi:10.1145/321864.321877.
- (bs) Penjić Safet, Seminarski rad - Tema: L i NL klase jezika, Univerzitet Sarajevo.
- (en) John E. Savage, Models Of Computation - Exploring the Power of Computing. ISBN 978-0-201-89539-1.